Basic Timestamp Ordering Protocol#
时间戳排序 （T/O） 是一类乐观的并发控制协议， DBMS 假定事务冲突很少见，不要求事务在允许对数据库对象进行读 / 写之前获取锁，而是使用时间戳来确定事务的串行顺序。
Basic T/O 使用 Timestamp 决定事务的先后顺序。
对于每个一行，会有另外的两个属性 Read ts 和 Write ts。
每个事务会记录一个开始时间戳。
通过比对事务的时间戳以及 Read ts 和 Write ts，可以检测到冲突。
loading...
读取流程
python
def read(r:Record):
if TX.startTS < r.WriteTS:
TX.reject() # reject and abort transaction
else:
TX.execution() # execution
r.WriteTS = max(r.WriteTS, TX.startTS)
写入流程：
python
def write(r:Record):
if TX.startTS < r.WriteTS or TX.startTS < r.ReadTS:
TX.reject() # reject and abort transaction
else:
TX.execution() # execution
r.WriteTS = TX.startTS
- 读写冲突，进行读取的事务会失败会滚
- 写读冲突，进行写入的事务会失败会滚
- 脏读，无法解决。
- 写写覆盖，后写入的事务会失败会滚
尽管 Basic T/O 用看似简单的方法解决了读写 / 写读 / 写写冲突，但是其修改是基于原有文件进行的，无法解决脏读的问题。
OCC#
OCC 如同其名称一样，是另外一种乐观并发控制协议，也使用时间戳去验证事务。OCC 适用于冲突较少的情况。比如事务都只进行读取或事访问的数据集不相交，在数据库很大且事务请求是均摊到数据集时，冲突的概率就很低。这种情况下，OCC 就是一种不错的选择。
OCC 会为每一个事务创建一个私有空间private workspace。所有事务中读到的对象会被复制进私有空间，所有的修改基于该私有空间进行，因此在将私有空间的修改提交前，任何修改都对外不可见。
在提交时，DBMS 比对事务在私有空间的写入数据，检查是否与其他事务冲突，如果没有冲突，提交就会被合并。
OCC 由三个阶段组成：
- Read：DBMS 为事务创建一个私有空间，追踪事务对数据的读写。
- Validation：事务提交时，DBMS 比对事务在私有空间的写入数据，检查是否与其他事务冲突。
- Write：如果经过验证没有冲突，DBMS 会将事务私有空间的修改合并到数据库，否则终止并重启事务。
loading...
验证方式：
每个事务在进入验证阶段时会被分配一个时间戳。为了确保只允许可串行化的事务执行，DBMS 会根据其他事务检查 Ti 是否存在 RW 和 WW 冲突，并确保所有冲突都采用单向方式（先来后到）。DBMS 检查提交事务与所有其他正在运行的事务的时间戳顺序。还未进入验证阶段的事务时间戳为infinity。如果Ti.TS > Tj.TS，则必须满足以下三个条件之一：
Ti在Tj开始前完成了所有的三个阶段。Ti在Tj进入Write阶段前完成了所有的三个阶段，且Ti没有修改Tj读取的任何对象。Ti先于Tj完成Read阶段，且Ti没有修改Tj读取或修改的任何对象。
可能问题：
- 数据复制到私有空间的成本很高。
- 验证 / 写入阶段瓶颈。
- 相比其他协议，事务中止会造成更多浪费，因为仅在事务执行后发生（仅在写入阶段发生）
- 在高并发条件下，时间戳分配瓶颈。